/**************************************************************************************************
* Title: SumPointerTree.h
* Author: Gael Huber
* Description: A tree containing pointer information about free blocks of space. Pointers refer to
*	the starting address of the usable space within a block.
**************************************************************************************************/
#ifndef __SUMPOINTERTREE_H__
#define __SUMPOINTERTREE_H__

#include "SumDataTypes.h"

class PointerTree {
public:

	// Inner class representative of a node
	class Node {
	public:
		// Constructor
		inline explicit Node(MemAddress ma)
			: parent(0), left(0), right(0), address(ma)
		{ }

		// Constructor where parent is specified
		inline explicit Node(Node* const p, MemAddress ma)
			: parent(p), left(0), right(0), address(ma)
		{ }

		// Destructor
		inline ~Node(void)
		{
			parent = 0;
			left = 0;
			right = 0;
		}

		// Return the parent node
		inline Node* const getParent(void) const
		{ return parent; }

		// Set the parent
		inline void setParent(Node* const value)
		{ parent = value; }

		// Return the left child
		inline Node* const getLeft(void) const
		{ return left; }

		// Set the left child
		inline void setLeft(Node* const value)
		{ left = value; }

		// Return the right child
		inline Node* const getRight(void) const
		{ return right;	}

		// Set the right child
		inline void setRight(Node* const value)
		{ right = value; }

		// Return the address of the represented memory block
		inline const MemAddress getAddress(void) const
		{ return address; }

		// Set the address
		inline void setAddress(const MemAddress value)
		{ address = value; }

	private:
		MemAddress address;	// Address of the memory block
		Node* parent;	// Parent node
		Node* left;		// Left child
		Node* right;	// Right child
	};

	// Constructor
	inline PointerTree(void)
		: root(0)
	{ }

	// Destructor, since consumed memory is part of a pre-allocated block, deallocation of memory does
	// not need to take place here.
	inline ~PointerTree(void)
	{ }

	void insert(Node* node);	// Insert a node into the tree
	void remove(Node* node);	// Remove a node from the tree
	const bool exists(MemAddress address) const;		// Check to see whether a node of a specified address exists
	Node* const find(MemAddress address) const;		// Returns the first node of a specified address
	const UINT32 depth(void) const;		// Calculate and return the depth of the tree
	const UINT32 size(void) const;		// Calculate and return the number of elements in the tree
	Node* const minimum(const Node* const node) const;	// Find the minimum node of the tree
	Node* const maximum(const Node* const node) const;	// Find the maximum node of the tree
	
	// Return the root node
	inline const Node* const getRoot(void) const
	{
		return root;
	}

private:
	void transplant(Node* u, Node* v);	// Transplant one node with another

	Node* root;		// Root node of the tree
};

#endif